package stringMultiply;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Stack;

public class Solution {
        public String multiply(String num1, String num2) {
            if (num1.equals("0") || num2.equals("0")) {
                return "0";
            }
            // 保存计算结果
            String res = "0";

            // num2 逐位与 num1 相乘
            for (int i = num2.length() - 1; i >= 0; i--) {
                int carry = 0;
                // 保存 num2 第i位数字与 num1 相乘的结果
                StringBuilder temp = new StringBuilder();
                // 补 0
                for (int j = 0; j < num2.length() - 1 - i; j++) {
                    temp.append(0);
                }
                int n2 = num2.charAt(i) - '0';

                // num2 的第 i 位数字 n2 与 num1 相乘
                for (int j = num1.length() - 1; j >= 0 || carry != 0; j--) {
                    int n1 = j < 0 ? 0 : num1.charAt(j) - '0';
                    int product = (n1 * n2 + carry) % 10;
                    temp.append(product);
                    carry = (n1 * n2 + carry) / 10;
                }
                // 将当前结果与新计算的结果求和作为新的结果
                res = addStrings(res, temp.reverse().toString());
            }
            return res;
        }

        /**
         * 对两个字符串数字进行相加，返回字符串形式的和
         */
        public String addStrings(String num1, String num2) {
            StringBuilder builder = new StringBuilder();
            int carry = 0;
            for (int i = num1.length() - 1, j = num2.length() - 1;
                 i >= 0 || j >= 0 || carry != 0;
                 i--, j--) {
                int x = i < 0 ? 0 : num1.charAt(i) - '0';
                int y = j < 0 ? 0 : num2.charAt(j) - '0';
                int sum = (x + y + carry) % 10;
                builder.append(sum);
                carry = (x + y + carry) / 10;
            }
            return builder.reverse().toString();
        }
//    public  static String multiply(String num1, String num2) {
//        if(num1.length()<num2.length()){
//            String tmp=num1;
//            num1=num2;
//            num2=tmp;
//        }
//        List<String> sts=new ArrayList<>();
//        int j=0;
//        for (int i = num2.length()-1; i >=0; i--,j++) {
//         StringBuilder sb=new StringBuilder();
//            for (int k = 0; k < j; k++) {
//                sb.append('0');
//            }
//            sb.append(singleMultiply(num1,num2.charAt(i)));
//            sts.add(sb.toString());
//        }
//
//        StringBuilder resb=new StringBuilder();
//        int t=0;//进位
//        for (int i = 0; i < sts.get(sts.size()-1).length(); i++) {
//            int sum=t;
//            for (int k = 0; k < sts.size(); k++) {//循环所有的数字
//                int value =0;
//                String str=sts.get(k);
//                if(i<str.length()){
//                    value=str.charAt(i)-'0';
//                }
//                sum+=value;
//            }
//            t=sum/10;
//            sum=sum%10;
//            char c=(char) (sum+'0');
//            resb.append(c);
//        }
//        if(t!=0){
//            resb.append((char)(t+'0'));
//        }
//        StringBuilder res=new StringBuilder();
//        String rs=resb.toString();
//        for (int i = rs.length()-1; i >= 0; i--) {
//            res.append(rs.charAt(i));
//        }
//        String r=res.toString();
//        if(r.charAt(0)=='0'){
//            return "0";
//        }
//        return r;
//    }
//    private static String singleMultiply(String num1,char num2){
//        StringBuilder sb=new StringBuilder();
//        int t=0;
//        for (int i = num1.length()-1; i>=0; i--) {
//            int a=num1.charAt(i)-'0'; //9
//            int b=num2-'0';
//            int mult=a*b+t;
//            t=mult/10;
//            mult=mult%10;
//            char c=(char) (mult+'0');//转换成字符'9'
//            sb.append(c);//19
//        }
//        if(t!=0){
//            sb.append(t);//198
//        }
//        return sb.toString();
//    }
}
// 121
// 121
//    121
//    0242
//    00121
//    14641

//    121
//   2420
//  12100
